class Solution(object):
    def numSquares(self, n):
        """
        :type n: int
        :rtype: int
        """
        # Lagrange 四平方定理： 任何一个正整数都可以表示成不超过四个整数的平方之和。
        # 满足四数平方和定理的数n（这里要满足由四个数构成，小于四个不行），必定满足 n=4a(8b+7) n = 4^a(8b + 7)n=4

        while n % 4 == 0:
            n /= 4
        while (n-7)%8 == 0:
            return 4
        # 比较两个数是不能组成n
        a = 0
        while a**2 <n:
            b = int((n - a**2)**0.5)
            if a**2 + b**2 == n:
                return (not not a) + (not not b)
            a += 1
        return 3
